/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/route-between-two-nodes-in-graph
   @Language: C++
   @Datetime: 16-02-09 08:27
   */

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */

// Method 1, DFS, Time 144ms
class Solution {
	bool hasRouteCore(unordered_set<DirectedGraphNode*> &vist
			,DirectedGraphNode *s,DirectedGraphNode *t){
		if (vist.find(s)!=vist.end()) return false;
		if (s==t) return true;
		vist.insert(s);

		for(const auto &n : s->neighbors)
			if (hasRouteCore(vist,n,t)) return true;
		return false;
	}

public:
	/**
	 * @param graph: A list of Directed graph node
	 * @param s: the starting Directed graph node
	 * @param t: the terminal Directed graph node
	 * @return: a boolean value
	 * Tip: Using hashset record visited nodes
	 * This Method DO NOT check node s and t are in graph.
	 *      The Serious Method MUST check s and t and their neighbors
	 *      whether are in graph!
	 */
	bool hasRoute(vector<DirectedGraphNode*> graph,
			DirectedGraphNode* s, DirectedGraphNode* t) {
		// write your code here
		unordered_set<DirectedGraphNode*> vist;
		return hasRouteCore(vist,s,t);
	}
};

// Method 2, BFS, Time 142ms
class Solution {
public:
	/**
	 * @param graph: A list of Directed graph node
	 * @param s: the starting Directed graph node
	 * @param t: the terminal Directed graph node
	 * @return: a boolean value
	 * Tip: Using hashset record visited nodes
	 * This Method DO NOT check node s and t are in graph.
	 *      The Serious Method MUST check s and t and their neighbors
	 *      whether are in graph!
	 */
	bool hasRoute(vector<DirectedGraphNode*> graph,
			DirectedGraphNode* s, DirectedGraphNode* t) {
		// write your code here
		unordered_set<DirectedGraphNode*> vist;
		queue<DirectedGraphNode*> que;
		for(que.push(s); que.size(); que.pop()){
			DirectedGraphNode *q = que.front();
			if (q==t) return true;
			vist.insert(q);
			for(const auto &n : q->neighbors)
				if (vist.find(n)==vist.end()) que.push(n);
		}
		return false;
	}
};
